package 牛客_面试必刷.Month07.day08;

public class 单链表的排序 {
    //选择排序的方式进行链表的重组
    public ListNode sortInList (ListNode head) {
        // write code here
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode key = temp;

        //开始找最小节点
        while(key.next != null){
            ListNode cur = key.next;
            ListNode pre = key;
            ListNode min = null;//最小值节点的下标标记
            ListNode pre_min = null;//最小值节点下标的前一个
            //先找到最小值节点
            while(cur != null){
                if(min == null || min.val > cur.val){
                    min = cur;
                    pre_min = pre;
                }
                cur = cur.next;
                pre = pre.next;
            }

            //然后开始进行节点的转移
            pre_min.next = min.next;
            min.next = key.next;
            key.next = min;
            key = key.next;
        }

        return temp.next;
    }
}
